#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0022.py
@time: 2021/9/16 15:16
@desc: https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
'''


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        if len(s) == 1:
            return 1
        n = len(s)
        dp = [0] * n
        dp[0] = 1
        for i in range(1, n):
            # 寻找(0, i)之间的与s[i]相同的字符的下表j
            j = -1
            for k in range(i):
                if s[k] == s[i]:
                    j = k
            # 如果 i-j < dp[i-1], 说明dp[j-1]的区间中有跟s[i]重复的字符
            # 那么 dp[j] = i-j
            if i - j <= dp[i - 1]:
                dp[i] = i - j

            # 如果 i-j > dp[j-1], 说明dp[j-1]的区间中没有跟s[i]重复的字符
            # 那么 dp[j] = dp[j-1] + 1，也就是可以算上s[i]而不重复
            elif i - j > dp[i - 1]:
                dp[i] = dp[i - 1] + 1

        return max(dp)

if __name__ == '__main__':
    sl = Solution()
    inp = "pwwkew"
    r = sl.lengthOfLongestSubstring(inp)
    print(r)